package com.zdp.leetcodeMiddle;

import com.zdp.util.ListNode;

/*
* 题目描述：
* 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
* 示例 1：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 删除链表的倒数第N个结点_19 {

    /*
    * 倒数第N个 不就是正数第Length-N+1个
    * 利用双指针，第一个指针先走n-1步，来到第n个结点
    * 此时，链表中还剩下 length-n个结点未遍历，总共可以走length-n+1步
    * 因为我们是从第一个结点开始遍历，所以只需要走length-n步即可（first.next!=null)
    * */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode p = head;
        ListNode first = head;
        ListNode pre = null;
        for(int i=1;i<n;i++){
            first = first.next;
        }
        while(first.next!=null){
            pre = p;
            p = p.next;
            first = first.next;
        }
        // 此时p正好指向要删除的结点
        // 注意边界条件
        if(p==head){
            head = head.next;
        }else{
            pre.next = p.next;
        }
        return head;
    }
}
